package org.lql.algo.codecrush.hot100.backtrack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author: liangqinglong
 * @date: 2025-08-31 10:52
 * @description: 17. 电话号码的字母组合 <a href="https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class LetterCombinations {

	private String digits;

	private Map<Character, String> alphabet;

	private List<String> ans;

	public List<String> letterCombinations(String digits) {
		this.digits = digits;
		alphabet = new HashMap<>();
		alphabet.put('2', "abc");
		alphabet.put('3', "def");
		alphabet.put('4', "ghi");
		alphabet.put('5', "jkl");
		alphabet.put('6', "mno");
		alphabet.put('7', "pqrs");
		alphabet.put('8', "tuv");
		alphabet.put('9', "wxyz");
		ans = new ArrayList<>();
		if (digits.isEmpty()) {
			return ans;
		}
		dfs(0, "");
		return ans;
	}

	public void dfs(int pos, String str) {
		if (pos == digits.length()) {
			ans.add(str);
			return;
		}
		String letters = alphabet.get(digits.charAt(pos));
		for (int i = 0; i < letters.length(); i++) {
			dfs(pos + 1, str + letters.charAt(i));
		}
	}

	public static void main(String[] args) {
		LetterCombinations letterCombinations = new LetterCombinations();
		System.out.println(letterCombinations.letterCombinations("23"));
	}
}
